package com.rui.study.algorithm.P_动态规划_最长递增子序列;

import java.util.Arrays;
import java.util.Random;

public class Solution1回溯法 {

    private int[] a;
    private int n;

    private int maxLen = Integer.MIN_VALUE;

    public Solution1回溯法(int[] a) {
        this.a = a;
        this.n = a.length;
    }

    public void maxLength(int tail, int i, int len) {

        if (i == n) {
            if (len > maxLen) maxLen = len;
            return;
        }

        // i不作子序列的尾
        maxLength(tail, i+1, len);

        // i作为子序列的尾
        if (a[i] >= a[tail]) {
            maxLength(i, i+1, len+1);
        } else {
            maxLength(i, i+1, 1);
        }
    }

    public static void main(String[] args) {
        int n = 32;
        int[] a = new int[n];
        Random r = new Random(31);
        for (int i = 0; i < n; i++) {
            a[i] = r.nextInt(n);
        }
        System.out.println(Arrays.toString(a));
        Solution1回溯法 solution = new Solution1回溯法(a);
        long start = System.currentTimeMillis();
        solution.maxLength(0,1,1);
        long end = System.currentTimeMillis();
        System.out.println("最长递增子序列长度：" + solution.maxLen + ", 耗时：[" + (end - start) + "ms]");
    }
}
